/*!
 * \mainpage ESI-10
 *
 * <h2>Componenti del gruppo</h2>
 *
 * - Davide Scola (s2299453)\n
 * - Minetti Alberto (s3064777)
 *
 * <hr>
 *
 * <h2>Dettagli Implementativi</h2>
 *
 * - Il linguaggio utilizzato per realizzare il progetto e` il <b>C++</b>
 *
 * <hr>
 *
 * <h2>Compilazione</h2>
 *
 * - La gestione dell'intero progetto e` stata realizzata utilizzando
 * <b>cmake</b>, per tanto la generazione dei <i>Makefile</i> viene ottenuta
 * invocando:\n
 * <b>cmake .</b>
 *
 * <hr>
 *
 * <h2>Documentazione</h2>
 *
 * - La documentazione del codice comprensiva di descrizione di tutte le funzioni
 * e` stata realizzata utilizzando <b>doxygen</b>; utilizzare <i>make doxygen</i>
 * per la generazione della stessa
 *
 * <hr>
 *
 * <h2>Risposte Esercitazione 1</h2>
 *
 * - Le risposte ai quesiti <b>1</b>, <b>2</b> e <b>3</b> dell'esercitazione sono
 * fornite sotto forma di test che e` possibile eseguire invocando <b>make test</b>;
 * si rimanda alla documentazione dei singoli test per la spiegazione di come i
 * risulati ottenuti siano stati verificati. In particolare si vedano i test:
 *  -# f[m]_reale
 *  -# f[m]_pari
 *  -# F[0]=17
 *  -# F_ok
 *  -# g[m]_reale
 *  -# g[m]_pari
 *  -# G[0]=33
 *  -# G_ok
 * 
 * - <b>Quesito 4</b>: Il diverso comportamento oscillante delle due <i>fft</i>
 * e` derivato dal <b>principio di indeterminazione</b> per il quale quando un
 * segnale si dilata la sua <i>dft</i> si concentra e viceversa. Infatti la
 * <i>dft</i> del segnale <b>F[m]</b>, che risulta piu` stretto, ha un'oscillazione
 * piu` ampia rispetto a quella del segnale <b>G[m]</b>.
 * 
 * <hr>
 * 
 * <h2>Grafici Esercitazione 1</h2>
 * 
 * - Tramite lo script <b>plotter</b> e` possibile visualizzare su di un grafico
 * la sovrapposizione della <i>fft</i> calcolata con lo schema a farfalla (in
 * blu) con quella calcolata con la formula teorica (in arancio).
 * 
 * - <b>F[x]</b>\n
 * \image html diagramma_fx.jpeg
 * 
 * - <b>G[x]</b>\n
 * \image html diagramma_gx.jpeg
 * 
 * <hr>
 * 
 * <h2>Risposte Esercitazione 2</h2>
 *
 * - Le risposte ai quesiti dell'esercitazione sono fornite sotto forma di test
 * che e` possibile eseguire invocando <b>make test</b>; si rimanda alla
 * documentazione dei singoli test per la spiegazione di come i risulati ottenuti
 * siano stati verificati. In particolare si vedano i test:
 *  -# F_inversa
 *  -# G_inversa
 * 
 * <hr>
 * 
 * <h2>Grafici Esercitazione 2</h2>
 * 
 * - Tramite lo script <b>plotter-inversa</b> e` possibile visualizzare su di un
 * grafico la sovrapposizione della <i>fft inversa</i> (in blu) con il segnale
 * originale (in arancio).
 * 
 * - <b>F<sup>-1</sup>[x]</b>\n
 * \image html inversa_fx.jpeg
 * 
 * - <b>G<sup>-1</sup>[x]</b>\n
 * \image html inversa_gx.jpeg
 *
 * <hr>
 * 
 * <h2>Grafici Esercitazione 2 (opzionale)</h2>
 *
 * - Tramite lo script <b>plotter-gauss</b> e` possibile visualizzare l'andamento del segnale
 * ti tipo gaussiano come riportato nel grafico sottostante:
 * 
 * \image html gaussian_signal.jpeg
 *
 * - Tramite lo script <b>plotter-fft-gauss</b> e` possibile visualizzare l'andamento
 * gaussiano della <i>FFT</i> come riportato dal grafico sottostante:
 *
 * \image html gaussian_fft.jpeg
 *
 * - Tramite lo script <b>plotter-gauss-varianze</b> e` possibile visualizzare l'andamento dei
 * vari segnali scelti in relazione alla varianza come riportato nel grafico sottostante:
 * \image html gaussian_varianze.jpeg
 *
 * - Tramite lo script <b>plotter-fft-varianze</b> e` possibile visualizzare l'andamento delle
 * <i>FFT</i> dei segnali di cui sopra. Prendendo come riferimento il grafico di cui sopra, notiamo
 * che la gaussiana con varianza minima, quindi la piu` dilatata, risulta avere una <i>FFT</i>
 * con un'oscillazione piu` stretta. In generale, in accordo con il <b>principio di indeterminazione</b>,
 * osserviamo che una maggiore varianza provoca una minore dilatazione della gaussiana e quindi
 * una maggiore dilatazione nella <i>FFT</i> come riportato dal grafico sottostante:
 *
 * \image html fft_gaussian_varianze.jpeg
 *
 * <hr>
 * 
 * <h2>Risposte Esercitazione 3</h2>
 *
 * - Le risposte ai quesiti dell'esercitazione sono fornite sotto forma di test;
 * si rimanda alla documentazione dei singoli test per la spiegazione di come i
 * risulati ottenuti siano stati verificati. In particolare si vedano i test:
 *  -# test-fft2D-proc1
 *  -# test-fft2D-proc2
 * 
 * <hr>
 * 
 * <h2>Grafici Esercitazione 3: procedura 1</h2>
 * 
 * - Il programma <b>test-fft2D-proc1</b>, una volta eseguito, calcola la FFT
 * dell'immagine "lena.raw" usando la procedura 1 e produce due file in output
 * (in formato raw) visibili qui in JPEG.
 * 
 * - <b>test-fft2D-proc1.jpg</b>\n
 * \image html test-fft2D-proc1.jpg
 * 
 * - <b>test-fft2D-INV-proc1.jpg</b>\n
 * \image html test-fft2D-INV-proc1.jpg
 *
 * <hr>
 * 
 * <h2>Grafici Esercitazione 3: procedura 2</h2>
 * 
 * - Il programma <b>test-fft2D-proc2</b>, una volta eseguito, calcola la FFT
 * dell'immagine "lena.raw" usando la procedura 2 e produce due file in output
 * (in formato raw) visibili qui in JPEG.
 * 
 * - <b>test-fft2D-proc1.jpg</b>\n
 * \image html test-fft2D-proc2.jpg
 * 
 * - <b>test-fft2D-INV-proc1.jpg</b>\n
 * \image html test-fft2D-INV-proc2.jpg
 *
 * <hr>
 * 
 * <h2>Risposte Esercitazione 4</h2>
 *
 * - Le risposte ai quesiti dell'esercitazione sono fornite sotto forma di test;
 * si rimanda alla documentazione dei singoli test per la spiegazione di come i
 * risulati ottenuti siano stati verificati. In particolare si vedano i test:
 *  -# test-random-numbers
 *  -# test-sinusoid
 *  -# test-parametric
 *
 * <hr>
 *
 * <h2>Grafici Esercitazione 4: seconda parte</h2>
 *
 * - <b>Quesito 1</b>: si e` scelto di campionare una sinusoide descritta
 * dalla funzione \f$S_x = sin( x )\f$ campionandola con <b>512</b> punti;
 * tramite lo script <b>plotter-sinusoid</b> e` possibile visualizzare su
 * di un grafico la sovrapposizione del <i>segnale pulito</i> (in blu) con
 * il <i>segnale rumoroso</i> (in arancio).
 *
 * \image html test-sinusoid.jpeg
 *
 * - <b>Quesito 2</b>: varie informazioni riguardo l'indice massimo, il
 * valore del segnale in tale punto e l'errore che si commetterebbe valutando
 * il segnale in quel punto vengono stampati dal programma <b>test-parametric</b>
 * direttamente in output preceduti da <i>#</i> in modo da poter continuare
 * ad usare <b>gnuplot</b> senza problemi
 *
 * - <b>Quesito 3</b>: il fattore di moltiplicazione e` stato ottenuto partendo
 * dalla formula:\n
 * \n
 * \f$E = \frac{ \sqrt{ f_m } }{ f_m }\f$ \n
 * \n
 * che puo` essere riscritta come:\n
 * \n
 * \f$E = \frac{ f_m^{ \frac{ 1 }{ 2 } } }{ f_m }\f$ \n
 * \n
 * da cui:\n
 * \n
 * \f$E = f_m^{ \frac{ 1 }{ 2 } - 1 }\f$ \n
 * \n
 * del tutto identica a:\n
 * \n
 * \f$E = f_m^{ \frac{ -1 }{ 2 } }\f$ \n
 * \n
 * ovvero sia:\n
 * \n
 * \f$E = \frac{ 1 }{ f_m^{ \frac{ 1 }{ 2 } } }\f$ \n
 * \n
 * sapendo, poi, che l'errore deve essere pari al <b>2%</b>, ovvero:\n
 * \n
 * \f$\frac{ 1 }{ f_m^{ \frac{ 1 }{ 2 } } } = 0.02\f$ \n
 * \n
 * ne consegue che:\n
 * \n
 * \f$f_m^{ \frac{ 1 }{ 2 } } = \frac{ 1 }{ 0.02 }\f$ \n
 * \n
 * e che quindi, infine:\n
 * \n
 * \f$f_m = (\frac{ 1 }{ 0.02 })^{ 2 }\f$ \n
 * \n
 * Dividendo, poi, tale valore per il valore massimo reale del segnale si
 * ottiene il coefficiente moltiplicativo desiderato. Tramite lo script
 * <b>plotter-parametric</b> e` possibile visualizzare su di un grafico la
 * sovrapposizione del <i>segnale pulito</i> (in blu) con il <i>segnale rumoroso</i>
 * (in arancio).
 *
 * \image html test-parametric.jpeg
 *
 * <hr>
 * 
 * <h2>Risposte Esercitazione 5</h2>
 *
 * - Le risposte ai quesiti dell'esercitazione sono fornite sotto forma di test;
 * si rimanda alla documentazione dei singoli test per la spiegazione di come i
 * risulati ottenuti siano stati verificati. In particolare si vedano i test:
 *  -# test-noisy-sinusoids
 *  -# test-filter-sinusoid
 *  -# test-cosinusoid
 *  -# test-filter-sosinusoid
 *
 * <hr>
 *
 * <h2>Grafici Esercitazione 5</h2>
 *
 * - <b>Quesito 2</b>: tramite lo script <b>plotter-noisy-sinusoids</b> e`
 * possibile visualizzare su di un grafico la sovrapposizione del
 * <i>segnale pulito</i> (in blu), descritto da \f$S_x = sin( x )\f$, con
 * il <i>segnale rumoroso</i> con noise gaussiano avente deviazione standard
 * pari al 5% del suo valore massimo (in arancio) ed il <i>segnale rumoroso</i>
 * con noise gaussiano avente deviazione standard pari al 10% del suo valore
 * massimo (in magenta).
 *
 * \image html test-noisy-sinusoids.jpeg
 *
 * - <b>Quesito 3</b>: tramite lo script <b>plotter-filter-sinusoid</b> e`
 * possibile visualizzare su di un grafico la sovrapposizione del <i>segnale
 * rumoroso</i> con noise gaussiano avente deviazione standard pari al 5% del
 * valore massimo della sinusoide (in blu) con il <i>segnale rumoroso</i>
 * con noise gaussiano avente deviazione standard pari al 10% del valore
 * massimo della sinusoide (in arancio) a cui e` stato applicato un filtro
 * passa-basso (annulla le frequenze alte del segnale).
 *
 * \image html test-filter-sinusoid.jpeg
 *
 * - <b>Quesito 5</b>: tramite lo script <b>plotter-cosinusoid</b> e` possibile
 * visualizzare su di un grafico la sovrapposizione del <i>segnale pulito</i> (in
 * blu), descritto da \f$S_x = cos( x )\f$, con il <i>segnale rumoroso</i> con
 * noise gaussiano avente deviazione standard pari al 5% del suo valore massimo
 * (in arancio).
 *
 * \image html test-cosinusoid.jpeg
 *
 * - <b>Quesito 6</b>: tramite lo script <b>plotter-filter-cosinusoid</b> e`
 * possibile visualizzare su di un grafico il solo rumore avente deviazione
 * standard pari al 5% del massimo della cosinusoide iniziale, ottenuto
 * applicando un filtro passa-alto al <i>segnale rumoroso</i> (dopo aver
 * trovato l'indice del massimo tralasciando la componente continua sono
 * stati azzerati i picchi per eliminare il segnale originale ed ottenere
 * il solo rumore).
 *
 * \image html test-filter-cosinusoid.jpeg
 */


/*!
 *  \file       Fft.hpp
 *  \brief      Definizione della classe \c Fft
 *  \author     Davide Scola <S2299453@studenti.unige.it>
 *  \author	Minetti Alberto <S3064777@studenti.unige.it>
 *  \version    1.0
 *
 */

#ifndef _FFT_H
#define _FFT_H

/*!
 *  \def    POWER_OF_2
 *  \brief  Calcola la potenza di due con l'esponente dato
 */
#define POWER_OF_2(x)		( (unsigned long int)(1 << (x)) )


/*!
 *  \brief      Definizione della classe \c Fft
 *
 */
template< class tType >
class Fft : public std::vector< std::complex< tType > > {
  public :
    typedef std::complex< tType > complex_t;
    
    Fft(const unsigned long int);
    void reset(const unsigned long int);
    void compute(const std::vector< tType >);
    void compute(const std::vector< complex_t >);
    bool isReal(void);
    bool isEven(void);
    void invert(void);
  
  protected :
    bool isPowerOfTwo( const unsigned long int );
    unsigned long int fastLog2(const unsigned long int);
    void bit_reversal(const unsigned long int, const unsigned long int, std::vector< unsigned long int >&);
    void doButterfly( std::vector< complex_t > );
    void doit( void );
  
  private :
    unsigned long int p;
    std::vector< unsigned long int > ind;
};

#endif              /* _FFT_H */
